package ch09_07;

import java.util.*;

class Pixel {
    int y;
    int x;
    public Pixel(int y, int x) {
	this.x = x;
	this.y = y;
    }
}

public class Solution {
	
	/**
	 * Good Question.
	 */
    public static void paintFill(char[][] screen, int y, int x, char color) {
	if (screen[y][x] == color)
	    return;
	int width = screen[0].length;
	int height = screen.length;
	Deque<Pixel> queue = new LinkedList<Pixel>();
	queue.addFirst(new Pixel(y, x));
	Set<Integer> visited = new HashSet<Integer>();
	int[] offsetX = {1, 0, -1, 0};
	int[] offsetY = {0, 1, 0, -1};
	char oldColor = screen[y][x];
	while (!queue.isEmpty()) {
	    Pixel top = queue.removeLast();
	    int key = top.y * width + top.x;
	    if (visited.contains(key))
		continue;
	    visited.add(key);
	    screen[top.y][top.x] = color;
	    for (int i = 0; i < offsetX.length; i++) {
		int yBa = top.y + offsetY[i];
		int xBa = top.x + offsetX[i];
		if (xBa < 0 || xBa >= width
		    || yBa < 0 || yBa >= height)
		    continue;
		if (screen[yBa][xBa] != oldColor)
		    continue;
		queue.addFirst(new Pixel(yBa, xBa));
	    }
	}
    }
    
    static char[] colors = {'B', 'G', 'R', 'Y'};
    
    public static char[][] initScreen(int height, int width) {
    	char[][] screen = new char[height][width];
    	
    	for (int i = 0; i < height; i++) {
    		for (int j = 0; j < width; j++) {
    			screen[i][j] = colors[(int)(Math.random() * colors.length)];
    		}
    	}
    	return screen;
    }
    
    public static void printScreen(char[][] screen) {
    	System.out.println("===============================");
    	for (int i = 0; i < screen.length; i++) {
    		for (int j = 0; j < screen[i].length; j++) {
    			System.out.print(screen[i][j]);
    		}
    		System.out.println();
    	}
    	System.out.println("==============================");
    }
    
    public static void main(String[] args) {
		int height = 5;
		int width = 10;
		char[][] screen = initScreen(height, width);
		printScreen(screen);
		int y = (int)(height * Math.random());
		int x = (int)(width * Math.random());
		char color = colors[(int)(colors.length * Math.random())];
		System.out.println("(y, x) is (" + y + ", " + x + "), color is " + color);
		paintFill(screen, y, x, color);
		printScreen(screen);
	}
}